package dfs;

import java.util.ArrayList;
import java.util.List;

/**
 * @author wcj
 * @Date 2021/7/6 17:30
 * @Version 1.0
 */
public class RecoveryIp {

    private static List<String> res;
    private static String[] str;
    private static String tmp;

    /**
     * 复原IP地址：给定一个只包含数字的字符串，找出其IP地址的组合，以点分十进制展示，注意：每一位不能以0开头
     * 深搜
     * ①递归方法的设计：dfs(int index,int depth)其中index表示当前访问到的字符索引，depth表示其当前层级
     * ②递归出口：(1)index == s.length() || depth == 4 截止,分情况
     * ③递归组合方式：因为每一位在0-256之间，所以每次组合1个/2个/3个字符
     *
     * @param s
     * @return
     */
    public static List<String> recoveryIp(String s) {
        res = new ArrayList<>();
        str = new String[4];
        tmp = s;
        dfs(0, 0);
        return res;
    }

    public static void dfs(int index, int depth) {
        // 递归截止条件
        if (index == tmp.length() || depth == 4) {
            if (index == tmp.length() && depth == 4) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 3; i++) {
                    sb.append(str[i] + ".");
                }
                sb.append(str[3]);
                res.add(sb.toString());
            }
            return;
        }
        // 递归组合方式
        for (int i = 1; i <= 3; i++) {
            // 注意这里需要是小于等于
            if (index + i <= tmp.length()) {
                String s = tmp.substring(index, index + i);
                if (isRight(s)) {
                    str[depth] = s;
                    dfs(index + i, depth + 1);
                    // 回溯
                    str[depth] = "";
                }
            }
        }
    }

    public static boolean isRight(String s) {
        if (s.equals("0") || (Integer.parseInt(s) > 0 && Integer.parseInt(s) < 256 && s.charAt(0) != '0')) {
            return true;
        }
        return false;
    }
}
